package gold.gold01;

import java.util.Stack;

/**
 * 在往栈里push的时候就排序好, 这样比较简单。如果是push的时候乱序, pop的时候再排序, 就比较麻烦。
 * 50, 注意一切对stack的循环pop操作, 都要对空栈进行考虑。
 * 也可以, 并不把另一个栈清空, 双单调栈, 一个栈全都是大于val的数, 另一个都是小于val的数。
 * 当pop的时候, 把第二个栈都塞给第一个栈。
 * 这样在有连续的push操作的时候会比较省时间, 在连续的pop操作时一样。
 * 这种判断和单调栈有点像
 */
public class S0305栈排序 {
    private Stack<Integer> stack0;
    private Stack<Integer> stack1;

    public S0305栈排序() {
        stack0 = new Stack<>();
        stack1 = new Stack<>();
    }

    public void push(int val) {
        if(isEmpty()){
            stack0.push(val);
            return;
        }
        while(!stack0.empty() && stack0.peek() < val){
            stack1.push(stack0.pop());
        }
        stack0.push(val);
        while (!stack1.empty()){
            stack0.push(stack1.pop());
        }
    }

    public void pop() {
        if(!isEmpty())
            stack0.pop();
    }

    public int peek() {
        if(isEmpty()) return -1;
        return stack0.peek();
    }

    public boolean isEmpty() {
        return stack0.isEmpty();
    }
}
